#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/3/7 14:15
# ===========================================
#       题目名称： 37. 解数独
#       题目地址： https://leetcode.cn/problems/sudoku-solver/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================

import copy
from sys import getsizeof
import itertools as _it
import psutil
import time

"""
    生成 找到含有的 然后再拼组    
"""

mem = psutil.virtual_memory()


class Solution:

    def sloveSudoku7(self, board):
        """
            3 * 3 从左往右延时法 for in range(len()) 比较消耗时间
            每次计算一下 3 * 3 内部的可能性 然后横向延伸
            完成时间 ： 2023年3月28日11:10:37
        """
        s = time.time()
        result = [
            ["5", "3", "4", "6", "7", "8", "9", "1", "2"],
            ["6", "7", "2", "1", "9", "5", "3", "4", "8"],
            ["1", "9", "8", "3", "4", "2", "5", "6", "7"],
            ["8", "5", "9", "7", "6", "1", "4", "2", "3"],
            ["4", "2", "6", "8", "5", "3", "7", "9", "1"],
            ["7", "1", "3", "9", "2", "4", "8", "5", "6"],
            ["9", "6", "1", "5", "3", "7", "2", "8", "4"],
            ["2", "8", "7", "4", "1", "9", "6", "3", "5"],
            ["3", "4", "5", "2", "8", "6", "1", "7", "9"]]

        const_step = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]  # 常量步数
        board_list = [board]  # 棋局
        cur_x, cur_y = 0, 0  # 当前 x y 的坐标
        while cur_x < 9 > cur_y:
            temp_board_list = []  # 临时棋局
            for temp_bl in board_list:
                temp_const_step = list(const_step)  # 临时常量步数
                contain_point_location = list()  # 记住带有点的位置
                # 3 * 3 符合规范的
                for x in range(cur_x, cur_x + 3):
                    for y in range(cur_y, cur_y + 3):
                        if temp_bl[x][y] == ".":
                            contain_point_location.append([x, y])  # 记录带有点的位置
                            continue
                        else:
                            temp_const_step.remove(temp_bl[x][y])  # 移除非法的
                # ---- 爲什麽把348 給排除了
                # 优化效率 记录一下 第几位不能是 几
                remember_list = [-1 for i in range(len(contain_point_location))]
                for element in _it.permutations(temp_const_step, len(contain_point_location)):

                    # 校验一下
                    next_step = True  # 进行下一步
                    for element_ind in range(len(element)):
                        if element[element_ind] == remember_list[element_ind]:
                            next_step = False
                            break
                    if not next_step:
                        continue

                    # 生成对应的排列组合 取符合条件的排列组合
                    is_ok = True
                    for i in range(len(contain_point_location)):
                        cur_point_location = contain_point_location[i]  # 当前点位置
                        x = cur_point_location[0]
                        y = cur_point_location[1]
                        # x
                        if is_ok and element[i] in temp_bl[x]:
                            remember_list[i] = element[i]
                            is_ok = False
                        # y
                        temp_board_y = []
                        for temp_x in range(len(temp_bl)):
                            temp_board_y.append(temp_bl[temp_x][y])
                        if is_ok and element[i] in temp_board_y:
                            remember_list[i] = element[i]
                            is_ok = False
                    if is_ok:
                        temp_board = copy.deepcopy(temp_bl)  # 临时棋盘
                        for i in range(len(contain_point_location)):  # 赋值
                            cur_point_location = contain_point_location[i]  # 当前点位置
                            x = cur_point_location[0]
                            y = cur_point_location[1]
                            temp_board[x][y] = element[i]
                        temp_board_list.append(temp_board)

            if temp_board_list:
                board_list = temp_board_list
            print(cur_x, cur_y, len(board_list), board_list[0].__str__().count('.'))
            # 重置以下坐标
            if cur_y + 3 < 9:
                cur_y += 3
            else:
                cur_x += 3
                cur_y = 0
        # 保持原有地址不变
        for x in range(len(board)):
            for y in range(len(board[x])):
                board[x][y] = board_list[0][x][y]
        print(time.time() - s, board)

    def sloveSudoku6(self, board):
        """
            3 * 3 从左往右延时法  效率不行
            每次计算一下 3 * 3 内部的可能性 然后横向延伸
            完成时间 ： 2023年3月28日11:10:37
        """
        s = time.time()
        result = [
            ["5", "3", "4", "6", "7", "8", "9", "1", "2"],
            ["6", "7", "2", "1", "9", "5", "3", "4", "8"],
            ["1", "9", "8", "3", "4", "2", "5", "6", "7"],
            ["8", "5", "9", "7", "6", "1", "4", "2", "3"],
            ["4", "2", "6", "8", "5", "3", "7", "9", "1"],
            ["7", "1", "3", "9", "2", "4", "8", "5", "6"],
            ["9", "6", "1", "5", "3", "7", "2", "8", "4"],
            ["2", "8", "7", "4", "1", "9", "6", "3", "5"],
            ["3", "4", "5", "2", "8", "6", "1", "7", "9"]]

        const_step = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]  # 常量步数
        board_list = [board]  # 棋局
        cur_x, cur_y = 0, 0  # 当前 x y 的坐标
        while cur_x < 9 > cur_y:
            temp_board_list = []  # 临时棋局
            for temp_bl_ind in range(len(board_list)):
                temp_bl = board_list[temp_bl_ind]
                temp_const_step = list(const_step)  # 临时常量步数
                contain_point_location = list()  # 记住带有点的位置
                # 3 * 3 符合规范的
                for x in range(cur_x, cur_x + 3):
                    for y in range(cur_y, cur_y + 3):
                        if temp_bl[x][y] == ".":
                            contain_point_location.append([x, y])  # 记录带有点的位置
                            continue
                        else:
                            temp_const_step.remove(temp_bl[x][y])  # 移除非法的
                # ---- 爲什麽把348 給排除了
                # 优化效率 记录一下 第几位不能是 几
                remember_list = [-1 for i in range(len(contain_point_location))]
                for element in _it.permutations(temp_const_step, len(contain_point_location)):
                    # 校验一下
                    next_step = True  # 进行下一步
                    for element_ind in range(len(element)):
                        if element[element_ind] == remember_list[element_ind]:
                            next_step = False
                            break
                    if not next_step:
                        continue

                    # 生成对应的排列组合 取符合条件的排列组合
                    is_ok = True
                    for i in range(len(contain_point_location)):
                        cur_point_location = contain_point_location[i]  # 当前点位置
                        x = cur_point_location[0]
                        y = cur_point_location[1]
                        # x
                        if is_ok and element[i] in temp_bl[x]:
                            remember_list[i] = element[i]
                            is_ok = False
                        # y
                        temp_board_y = []
                        for temp_x in range(len(temp_bl)):
                            temp_board_y.append(temp_bl[temp_x][y])
                        if is_ok and element[i] in temp_board_y:
                            remember_list[i] = element[i]
                            is_ok = False
                    if is_ok:
                        temp_board = copy.deepcopy(temp_bl)  # 临时棋盘
                        for i in range(len(contain_point_location)):  # 赋值
                            cur_point_location = contain_point_location[i]  # 当前点位置
                            x = cur_point_location[0]
                            y = cur_point_location[1]
                            temp_board[x][y] = element[i]
                        temp_board_list.append(temp_board)

            if temp_board_list:
                board_list = temp_board_list
            print(cur_x, cur_y, len(board_list), board_list[0].__str__().count('.'))
            # 重置以下坐标
            if cur_y + 3 < 9:
                cur_y += 3
            else:
                cur_x += 3
                cur_y = 0
        # 保持原有地址不变
        for x in range(len(board)):
            for y in range(len(board[x])):
                board[x][y] = board_list[0][x][y]
        print(time.time() - s, board)

    def sloveSudoku5(self, board):
        """
            3 * 3 从左往右延时法 超出时间限制
            每次计算一下 3 * 3 内部的可能性 然后横向延伸
            完成时间 ： 2023年3月28日11:10:37
        """
        const_step = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]  # 常量步数
        board_list = [board]  # 棋局
        cur_x, cur_y = 0, 0  # 当前 x y 的坐标
        while cur_x < 9 > cur_y:
            temp_board_list = []  # 临时棋局
            for temp_bl_ind in range(len(board_list)):
                temp_bl = board_list[temp_bl_ind]
                temp_const_step = copy.deepcopy(const_step)  # 临时常量步数
                contain_point_location = []  # 记住带有点的位置
                # 3 * 3 符合规范的
                for x in range(cur_x, cur_x + 3):
                    for y in range(cur_y, cur_y + 3):
                        if temp_bl[x][y] == ".":
                            contain_point_location.append([x, y])  # 记录带有点的位置
                            continue
                        else:
                            temp_const_step.remove(temp_bl[x][y])  # 移除非法的
                # ---- 爲什麽把348 給排除了
                for element in _it.permutations(temp_const_step, len(contain_point_location)):
                    # 生成对应的排列组合 取符合条件的排列组合
                    is_ok = True
                    for i in range(len(contain_point_location)):
                        cur_point_location = contain_point_location[i]  # 当前点位置
                        # x
                        if is_ok and element[i] in temp_bl[cur_point_location[0]]:
                            is_ok = False
                        # y
                        temp_board_y = []
                        for temp_x in range(len(temp_bl)):
                            temp_board_y.append(temp_bl[temp_x][cur_point_location[1]])
                        if is_ok and element[i] in temp_board_y:
                            is_ok = False
                    if is_ok:
                        temp_board = copy.deepcopy(temp_bl)  # 临时棋盘
                        for i in range(len(contain_point_location)):  # 赋值
                            cur_point_location = contain_point_location[i]  # 当前点位置
                            x = cur_point_location[0]
                            y = cur_point_location[1]
                            temp_board[x][y] = element[i]
                        temp_board_list.append(temp_board)

            if temp_board_list:
                board_list = temp_board_list
            print(cur_x, cur_y, len(board_list), board_list[0].__str__().count('.'))
            # 重置以下坐标
            if cur_y + 3 < 9:
                cur_y += 3
            else:
                cur_x += 3
                cur_y = 0
        # 保持原有地址不变
        for x in range(len(board)):
            for y in range(len(board[x])):
                board[x][y] = board_list[0][x][y]

    def solveSudoku4(self, board):
        """
            电脑死机
        """
        availables = ("0", "1", "2", "3", "4", "5", "6", "7", "8", "9")
        # 全部数独的可能性
        boards_list = list(list())
        boards_list.append(board)
        # x, y 当前坐标
        x, y = 0, 0
        while x < 9 > y:
            # 临时棋盘
            boards_list_tmp = list(list())

            print(""
                  "当前x ->" + str(x) + " y ->" + str(y) +
                  " 棋盘出现的可能性：" + str(len(boards_list)) +
                  "，当前操作系统内存还剩余：%.4f" % (float(mem.free) / 1024 / 1024 / 1024))
            for i in range(len(boards_list)):
                if i > 0 and i % 100000 == 0:
                    print("当前已执行10万条数据，boards_list占用内存：" + str(
                        getsizeof(boards_list) / 1024) + "KB  boards_list_tmp占用内存：" + str(
                        getsizeof(boards_list_tmp) / 1024) + "KB")
                # 第 i 局棋盘
                board_i = boards_list[i]
                # print(board_i)
                # 当前还剩余可以走的棋
                remain_availables = copy.deepcopy(list(availables))
                if board_i[x][y] == ".":
                    # 排除x
                    for col in board_i[x]:
                        if col in remain_availables:
                            remain_availables.remove(col)
                    # 排除y
                    for board_i_line in board_i:
                        if board_i_line[y] in remain_availables:
                            remain_availables.remove(board_i_line[y])
                    # 排除3 *3
                    # 三三  划分三三区域 0,3 -> 0,0   7,4->6,3
                    # 0,0  0,3  0,6
                    # 3,0  3,3  3,6
                    # 6,0  6,3  6,6
                    x_origin_seat, y_origin_seat = (x // 3) * 3, (y // 3) * 3  # x起始位置  y 起始位置
                    for m in range(x_origin_seat, x_origin_seat + 3):
                        for n in range(y_origin_seat, y_origin_seat + 3):
                            if board_i[m][n] in remain_availables:
                                remain_availables.remove(board_i[m][n])
                    # 剩余可以走的棋子
                    if remain_availables:
                        for remain_available in remain_availables:
                            board_i_tmp = copy.deepcopy(board_i)
                            board_i_tmp[x][y] = remain_available
                            boards_list_tmp.append(board_i_tmp)
                else:
                    if y + 1 >= 9:
                        x += 1
                        y = 0
                    else:
                        y += 1
            if boards_list_tmp:
                boards_list.clear()
                boards_list.extend(boards_list_tmp)
        print(boards_list)

    def solveSudoku3(self, board):
        """
            Do not return anything, modify board in-place instead.
            步步蚕食 向对角靠拢
            —— —— —— >
            |   —— ——>
            |   |   ——>
            |   |   |
            V   V   V
        """
        # 数独常量
        sd_const_tuple = ("0", "1", "2", "3", "4", "5", "6", "7", "8", "9")
        # 棋盘全部可能性
        board_all_list = list()
        board_all_list.append(board)
        # 位置current_seat(x,y) 默认0行 第一个点  MAX_LEN 最大长度
        current_seat_list, MAX_LEN = [0, board[0].index(".")], 9
        while current_seat_list[0] < MAX_LEN and current_seat_list[1] < MAX_LEN:
            # 存放下一次 棋盘全部可能性
            next_board_all_list = list(list())

            for current_index in range(len(board_all_list)):
                # 当前棋盘
                current_board = copy.deepcopy(board_all_list[current_index])
                # 判断这局棋下一步可以怎么走
                # 当前棋局已经走了那几步
                current_board_go_list = list()

                # x 列 深拷贝 防止元数据被篡改
                current_board_x = current_board[current_seat_list[0]]
                # y
                current_board_y = [current_board[i][current_seat_list[1]] for i in range(MAX_LEN)]
                # 33
                # 三三  划分三三区域 0,3 -> 0,0   7,4->6,3
                # 0,0  0,3  0,6
                # 3,0  3,3  3,6
                # 6,0  6,3  6,6
                current_board_ss = []
                x_origin_seat, y_origin_seat = (current_seat_list[0] // 3) * 3, (
                        current_seat_list[1] // 3) * 3  # x起始位置  y 起始位置
                for i in range(x_origin_seat, x_origin_seat + 3):
                    for j in range(y_origin_seat, y_origin_seat + 3):
                        current_board_ss.append(current_board[i][j])
                # 三条合并
                current_board_go_list = list(set(current_board_x + current_board_y + current_board_ss))

                # 排除已经走的
                for i in range(len(sd_const_tuple)):
                    step = sd_const_tuple[i]
                    if current_board_go_list.count(step) == 0:
                        current_board_tmp = copy.deepcopy(current_board)
                        current_board_tmp[current_seat_list[0]][current_seat_list[1]] = step
                        next_board_all_list.append(current_board_tmp)
            # 记录一下
            if next_board_all_list:
                board_all_list = next_board_all_list
            # 变动位置
            if next_board_all_list[0][current_seat_list[0]].count(".") > 0:
                current_seat_list[1] = next_board_all_list[0][current_seat_list[0]].index(".")
            else:
                current_seat_list[0] = current_seat_list[0] + 1
                current_seat_list[1] = next_board_all_list[0][current_seat_list[0]].index(".")
            print("位置变动了 => ", current_seat_list, "动态生成了多少种棋盘： =>", len(board_all_list))

    def solveSudoku(self, board):
        """
            Do not return anything, modify board in-place instead.
        """
        # 数独常量不重复集合
        sd_const_set = {"1", "2", "3", "4", "5", "6", "7", "8", "9"}
        # 记录一下临时棋盘
        tmp_boards = list()
        tmp_boards.append(board)
        # x,y 轴  max_x max_y 最大值
        x, y, max_len = 0, 0, len(board)
        while x < max_len > y:
            # 找到 带 . 的地方
            if board[x][y] == ".":
                # 记录下一次遍历有用的棋盘
                next_loop_list = list()
                # 循环遍历没一盘棋
                current_board_index = 0
                while current_board_index < len(tmp_boards):
                    current_board = tmp_boards[current_board_index]
                    # 排除该棋局 x y 三三 重复的数据
                    current_sd_const_set = copy.deepcopy(sd_const_set)
                    tmp_x_board, tmp_y_board, tmp_ss_board = set(), set(), set()
                    # x
                    for i in range(max_len):
                        if current_board[x][i] != ".":
                            cp = copy.deepcopy(current_board[x][i])
                            tmp_x_board.add(cp)
                    current_sd_const_set.difference_update(tmp_x_board)
                    if not current_sd_const_set:
                        current_board_index += 1
                        continue
                    # y
                    for i in range(max_len):
                        if current_board[i][y] != ".":
                            cp = copy.deepcopy(current_board[i][y])
                            tmp_y_board.add(cp)
                    current_sd_const_set.difference_update(tmp_y_board)
                    if not current_sd_const_set:
                        current_board_index += 1
                        continue
                    # 三三  划分三三区域 0,3 -> 0,0   7,4->6,3
                    # 0,0  0,3  0,6
                    # 3,0  3,3  3,6
                    # 6,0  6,3  6,6
                    x_origin_seat, y_origin_seat = (x // 3) * 3, (y // 3) * 3  # x起始位置  y 起始位置
                    for i in range(x_origin_seat, x_origin_seat + 3):
                        for j in range(y_origin_seat, y_origin_seat + 3):
                            if current_board[i][j] != ".":
                                cp = copy.deepcopy(current_board[i][j])
                                tmp_ss_board.add(cp)
                    current_sd_const_set.difference_update(tmp_ss_board)
                    if not current_sd_const_set:
                        current_board_index += 1
                        continue
                    print(x, y, current_sd_const_set)
                    for tmp_sd_const in current_sd_const_set:
                        tmp_current_board = copy.deepcopy(current_board)  # 此处必须为深拷贝
                        tmp_current_board[x][y] = tmp_sd_const
                        next_loop_list.append(tmp_current_board)
                    current_board_index += 1
                if next_loop_list:
                    tmp_boards = copy.deepcopy(next_loop_list)
            # 增加边界
            if y + 1 < max_len:
                y += 1
            else:
                if x + 1 < max_len:
                    x += 1
                    y = 0
                else:
                    break
        if tmp_boards and len(tmp_boards) == 1:
            for x in range(len(board)):
                for y in range(len(board[x])):
                    board[x][y] = tmp_boards[0][x][y]
        print(board)


if __name__ == "__main__":
    board = [["5", "3", ".", ".", "7", ".", ".", ".", "."],
             ["6", ".", ".", "1", "9", "5", ".", ".", "."],
             [".", "9", "8", ".", ".", ".", ".", "6", "."],
             ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
             ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
             ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
             [".", "6", ".", ".", ".", ".", "2", "8", "."],
             [".", ".", ".", "4", "1", "9", ".", ".", "5"],
             [".", ".", ".", ".", "8", ".", ".", "7", "9"]]
    board2 = [[".", ".", "9", "7", "4", "8", ".", ".", "."],
              ["7", ".", ".", ".", ".", ".", ".", ".", "."],
              [".", "2", ".", "1", ".", "9", ".", ".", "."],
              [".", ".", "7", ".", ".", ".", "2", "4", "."],
              [".", "6", "4", ".", "1", ".", "5", "9", "."],
              [".", "9", "8", ".", ".", ".", "3", ".", "."],
              [".", ".", ".", "8", ".", "3", ".", "2", "."],
              [".", ".", ".", ".", ".", ".", ".", ".", "6"],
              [".", ".", ".", "2", "7", "5", "9", ".", "."]]
    s = Solution()
    s.solveSudoku(board2)
